package com.sheng.leetcode.year2023.month03.day23;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author liusheng
 * @date 2023/03/23
 * <p>
 * 1630. 等差子数组<p>
 * <p>
 * 如果一个数列由至少两个元素组成，且每两个连续元素之间的差值都相同，那么这个序列就是 等差数列 。<p>
 * 更正式地，数列 s 是等差数列，只需要满足：对于每个有效的 i ， s[i+1] - s[i] == s[1] - s[0] 都成立。<p>
 * 例如，下面这些都是 等差数列 ：<p>
 * 1, 3, 5, 7, 9<p>
 * 7, 7, 7, 7<p>
 * 3, -1, -5, -9<p>
 * 下面的数列 不是等差数列 ：<p>
 * 1, 1, 2, 5, 7<p>
 * 给你一个由 n 个整数组成的数组 nums，和两个由 m 个整数组成的数组 l 和 r，后两个数组表示 m 组范围查询，<p>
 * 其中第 i 个查询对应范围 [l[i], r[i]] 。所有数组的下标都是 从 0 开始 的。<p>
 * 返回 boolean 元素构成的答案列表 answer 。如果子数组 nums[l[i]], nums[l[i]+1], ... , nums[r[i]]<p>
 * 可以 重新排列 形成 等差数列 ，answer[i] 的值就是 true；否则answer[i] 的值就是 false 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5]<p>
 * 输出：[true,false,true]<p>
 * 解释：<p>
 * 第 0 个查询，对应子数组 [4,6,5] 。可以重新排列为等差数列 [6,5,4] 。<p>
 * 第 1 个查询，对应子数组 [4,6,5,9] 。无法重新排列形成等差数列。<p>
 * 第 2 个查询，对应子数组 [5,9,3,7] 。可以重新排列为等差数列 [3,5,7,9] 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10], l = [0,1,6,4,8,7], r = [4,4,9,7,9,10]<p>
 * 输出：[false,true,false,false,true,true]<p>
 * <p>
 * 提示：<p>
 * n == nums.length<p>
 * m == l.length<p>
 * m == r.length<p>
 * 2 <= n <= 500<p>
 * 1 <= m <= 500<p>
 * 0 <= l[i] < r[i] < n<p>
 * -10^5 <= nums[i] <= 10^5<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/arithmetic-subarrays">1630. 等差子数组</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1630 {

    @Test
    public void test01() {
//        int[] nums = {4, 6, 5, 9, 3, 7}, l = {0, 0, 2}, r = {2, 3, 5};
        int[] nums = {-12, -9, -3, -12, -6, 15, 20, -25, -20, -15, -10}, l = {0, 1, 6, 4, 8, 7}, r = {4, 4, 9, 7, 9, 10};
        System.out.println(new Solution().checkArithmeticSubarrays(nums, l, r));
    }
}

class Solution {
    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        List<Boolean> answer = new ArrayList<>();
        boolean flag;
        for (int i = 0; i < l.length; i++) {
            // 获取数组 nums 对应的子数组
            int[] ints = Arrays.copyOfRange(nums, l[i], r[i] + 1);
            // 对子数组进行排序
            Arrays.sort(ints);
            flag = true;
            // 循环判断是否满足条件
            for (int j = 1; j < ints.length; j++) {
                if (ints[1] - ints[0] != ints[j] - ints[j - 1]) {
                    flag = false;
                    break;
                }
            }
            answer.add(flag);
        }
        return answer;
    }
}
